package org.example.leetcode;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/04/26 9:37
 */


//实现支持下列接口的「快照数组」- SnapshotArray：
//
//
// SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。
// void set(index, val) - 会将指定索引 index 处的元素设置为 val。
// int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
// int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。
//
//
//
//
// 示例：
//
// 输入：["SnapshotArray","set","snap","set","get"]
//     [[3],[0,5],[],[0,6],[0,0]]
//输出：[null,null,0,null,5]
//解释：
//SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
//snapshotArr.set(0,5);  // 令 array[0] = 5
//snapshotArr.snap();  // 获取快照，返回 snap_id = 0
//snapshotArr.set(0,6);
//snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5
//
//
//
// 提示：
//
//
// 1 <= length <= 50000
// 题目最多进行50000 次set，snap，和 get的调用 。
// 0 <= index < length
// 0 <= snap_id < 我们调用 snap() 的总次数
// 0 <= val <= 10^9
//
//
// Related Topics 设计 数组 哈希表 二分查找 👍 136 👎 0



import javafx.util.Pair;

import java.util.*;

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.set(index,val);
 * int param_2 = obj.snap();
 * int param_3 = obj.get(index,snap_id);
 */
//leetcode submit region end(Prohibit modification and deletion)
@Deprecated
public class SnapshotArray1146 {

    public static void main(String[] args) {
        SnapshotArray2 snapshotArr = new SnapshotArray2(4);
        snapshotArr.snap();
        snapshotArr.snap();
        System.out.println(snapshotArr.get(3,1));
        // 初始化一个长度为 3 的快照数组
        snapshotArr.set(0,5);
        // 令 array[0] = 5

        // 获取快照，返回 snap_id = 0
        snapshotArr.set(0,6);
        System.out.println(snapshotArr.get(0,0));
        // 获取 snap_id = 0 的快照中
        // array[0] 的值，返回 5
    }


    static class SnapshotArray2{

        private int curSnapId;

        private HashMap<Integer, List<Pair<Integer, Integer>>> snapMap = new HashMap<>();

        public SnapshotArray2(int length) {
            curSnapId = 0;
        }

        public void set(int index, int val) {
            if(snapMap.get(index) == null){
                List<Pair<Integer, Integer>> historyList = new ArrayList<>();
                snapMap.put(index, historyList);
            }
            snapMap.get(index).add(new Pair<>(curSnapId, val));
        }

        public int snap() {
           return curSnapId++;
        }

        public int get(int index, int snap_id) {
            if (!snapMap.containsKey(index)) {
                return 0;
            }

            List<Pair<Integer, Integer>> historyList = snapMap.get(index);
            int historyIndex = getHistoryIndex(historyList, snap_id);
            return historyIndex == -1 ? 0 : historyList.get(historyIndex).getValue();
        }

        private int getHistoryIndex(List<Pair<Integer, Integer>> historyList, int snapId) {

            if(historyList.isEmpty()){
                return -1;
            }

            int left = -1;
            int right = historyList.size();

            while (left+1<right){
                int mid = left + (right - left) / 2;
                if(historyList.get(mid).getKey() > snapId){
                    right = mid;
                }else{
                    left = mid;
                }
            }

            return left;

        }
    }

    @Deprecated
    static class SnapshotArray{

        private Integer[] base;

        private HashMap<Integer, Integer> baseMap = new HashMap<>();
        private HashMap<Integer, HashMap<Integer, Integer>> snapMap = new HashMap<>();

        public SnapshotArray(int length) {
            base = new Integer[length];
        }

        public void set(int index, int val) {
            base[index] = val;
            baseMap.put(index,val);
        }

        public int snap() {
            HashMap<Integer, Integer> copyMap = new HashMap<>(baseMap);
            snapMap.put(snapMap.size(), copyMap);
            return snapMap.size() - 1;
        }

        public int get(int index, int snap_id) {
            if(snapMap.get(snap_id) == null){
                return 0;
            }
            if(snapMap.get(snap_id).get(index) == null){
                return 0;
            }
            return snapMap.get(snap_id).get(index);
        }

    }

}

